// 快排原理和荷兰国旗原理差不多，时间复杂度为O(N*logN)
const quickSort = (arr: Array<number>) => {
    if(arr === null || arr.length < 2) return
    process(arr,0,arr.length-1)
}
const process = (arr:Array<number>, L:number,R: number)=>{
    if(L < R){
        swap(arr,L+Math.floor(Math.random()*(R-L+1)),R)
        const p = partition(arr,L,R)
        process(arr,L,p[0]-1)
        process(arr,p[1]+1,R)
    }
}
const swap = (arr:Array<number>, i:number,j: number)=>{
    let num = 0
    num = arr[i] 
    arr[i] = arr[j]
    arr[j] = num
}
const partition = (arr:Array<number>,L:number,R:number)=>{
    let less = L - 1    //-1
    let more = R        //8
    while(L < more) {   //0 8 7 6
        if(arr[L] < arr[R]){ 
            swap(arr,++less,L++)
        }else if(arr[L] > arr[R]){
            swap(arr,--more,L)
        }else{
            L++
        }
    }
    swap(arr,more,R)
    return [less+1,more]
}
let arr = [2,3,4,1,2,7,5,2,4]
quickSort(arr)
console.log(arr)
export default quickSort